#pragma once
#include <iostream>
#include <vector>
#include <string>
#include <assert.h>
#include<time.h>
#include <utility> 
#include <iostream>

using namespace std;
#define RED 1
#define BLACK 2

//从现在开始将T当作data看待，data含有Key数据和Value数据
template<class T>
struct RBTreeNode {//采用的是三叉链，存储的类型为pair<K,V>
    T _data;
    RBTreeNode* _right;
    RBTreeNode* _left;
    RBTreeNode* _parent;
    int _color;

    //默认构造
    RBTreeNode(const T& data = T())
        :_data(data)
        , _right(nullptr)
        , _left(nullptr)
        , _parent(nullptr)
        , _color(RED)
    {}

};

//T这里传的是就是T，例如Map的T是pair<Key,Value>，Set的T是key
template<class T, class Ptr, class Ref>
class __RBTreeiterator
{
public:
    typedef RBTreeNode<T>Node;
    typedef __RBTreeiterator<T, Ptr, Ref> Self;
    typedef __RBTreeiterator<T, T*, T&> iterator;//一定是一个普通迭代器

    Node* _node;//_node就是节点的指针，是迭代器封装的核心

        //由于iterator一定是一个普通迭代器，因此用const修饰该普通迭代器就一定是一个const迭代器
        //此时 const迭代器 it里的值全部都具有const属性，能直接给set
        //正常情况下，传给set的iterator是一个普通迭代器，而set本身只有const迭代器，因此会传参失败
    __RBTreeiterator(const iterator& it)
        :_node(it._node)
    {}
    __RBTreeiterator(Node* node)
        :_node(node)
    {}
    

    Ref operator*()
    {
        return (*_node)._data;//先获得_data本身，返回值用引用去接收，即可获得_data的别名
    }

    Ptr operator->()
    {
        return &(operator*());//先获得_data本身（看做是本身）再用取地址符获得地址
    }
    Self& operator++()
    {
        //1.右子树不为空，去找右子树中的最小值
        //2.右子树为空，去找祖先里：本身节点是父节点的左节点---的节点
        //   如果父节点为空了，则退出查找，并返回空

            if (_node->_right)
            {
                Node* RightMin = _node->_right;
                while (RightMin->_left)
                {
                    RightMin = RightMin->_left;
                }
                //此时RightMin是右树中最小的值
                _node = RightMin;
            }
            else//右子树为空的情况
            {
                Node* cur = _node;
                Node* parent = cur->_parent;
                while (parent)
                {
                    if (cur == parent->_left)
                    {
                        break;
                    }
                    else if (cur == parent->_right)
                    {
                        cur = parent;
                        parent = parent->_parent;
                    }
                }
                _node = parent;//_node要么为空没找到，要么不为空找到了对应++的位置
            }
            return *this;
    }

    Self operator++(int)
    {
        __RBTreeiterator temp(_node);
        operator++();
        return temp;
    }

    Self& operator--()
    {
        //1.左子树不为空，找左子树中最大的一个
        //2.左子树为空，去找祖先里：本身节点是父节点的右节点---的节点
        //   如果父节点为空了，则退出查找，并返回空
        if (_node->_right)
        {
            Node* LeftMax = _node->_left;
            while (LeftMax->_right)
            {
                LeftMax = LeftMax->_right;
            }
            //此时RightMin是右树中最小的值
            _node = LeftMax;
        }
        else//右子树为空的情况
        {
            Node* cur = _node;
            Node* parent = cur->_parent;
            while (parent)
            {
                if (cur == parent->_right)
                {
                    break;
                }
                else if (cur == parent->_left)
                {
                    cur = parent;
                    parent = parent->_parent;
                }
            }
            _node = parent;//_node要么为空没找到，要么不为空找到了对应++的位置
        }
        return *this;
    }

    Self operator--(int)
    {
        __RBTreeiterator temp(_node);
        operator--();
        return temp;
    }

    bool operator!=(const Self& s) const
    {
        return _node != s._node;
    }
};

template<class K, class T, class GetKey>
class RBTree
{
public:
    typedef RBTreeNode<T> Node;
    typedef __RBTreeiterator<T, T*, T&> iterator;
    typedef __RBTreeiterator<T, const T*, const T&> const_iterator;

private:
    //成员
    Node* _root;


public:
    RBTree()//默认构造
        :_root(nullptr)
    {}

    RBTree(const T& node)//构造函数
        :_root(nullptr)
    {
        insert(node);
    }



    pair<iterator, bool> insert(const T& node)
    {
        GetKey kot;
        Node* cur = _root;
        Node* parent = nullptr;
        //如果树中为空
        if (cur == nullptr) {//new一个节点后直接return返回
            _root = new Node(node);
            _root->_color == BLACK;
            return make_pair(iterator(_root),true);
        }
        //如果不为空
        else {
            while (cur)//只要cur不为空就一直往下走,直到cur为空时，才是要插入的位置
            {
                if (kot(node) > kot(cur->_data)) {//如果插入的数比cur大，就放到右边
                    parent = cur;
                    cur = cur->_right;
                }
                else if (kot(node) < kot(cur->_data)) {//如果插入的数比cur小，就放到左边
                    parent = cur;
                    cur = cur->_left;
                }
                else {//如果插入的数相同了，直接return false
                    return make_pair(iterator(cur), false);
                }

                //当cur为空时，可以退出循环，准备插入工作
            }
            //插入cur
            Node* newnode = new Node(node);
            if (kot(node) > kot(parent->_data)) { parent->_right = newnode; }//插入在右子树时
            else if (kot(node) < kot(parent->_data)) { parent->_left = newnode; }//插入在左子树时
            cur = newnode;
            cur->_parent = parent;
        }
        //至此，插入完成--------------------------------------------------------------------------
        //插入后，cur是新节点，parent是新节点的父节点
        Node* temp = cur;

        while (parent && parent->_color == RED)
        {
            Node* grandfather = parent->_parent;
            //当parent是grandfather的左节点
            if (grandfather && parent == grandfather->_left)
            {
                Node* uncle = grandfather->_right;
                if (uncle && uncle->_color == RED)//uncle存在并为红
                {
                    parent->_color = uncle->_color = BLACK;
                    grandfather->_color = RED;
                    cur = grandfather;
                    parent = cur->_parent;
                    //继续往上判断
                }
                else//uncle不存在 或者 存在且为黑
                {
                    if (cur == parent->_right)//需要双旋
                    {
                        RotateL(parent);
                        RotateR(grandfather);
                        cur->_color = BLACK;
                        grandfather->_color = RED;
                    }
                    else//需要单旋
                    {
                        RotateR(grandfather);
                        parent->_color = BLACK;
                        grandfather->_color = RED;
                    }

                    break;
                }
            }
            //当parent是grandfather的右节点
            else if (grandfather && parent == grandfather->_right)
            {
                Node* uncle = grandfather->_left;
                if (uncle && uncle->_color == RED)//uncle存在并为红
                {
                    parent->_color = uncle->_color = BLACK;
                    grandfather->_color = RED;
                    cur = grandfather;
                    parent = cur->_parent;
                    //继续往上判断
                }
                else//uncle不存在 或者 存在且为黑
                {
                    if (cur == parent->_left)//需要双旋
                    {
                        RotateR(parent);
                        RotateL(grandfather);
                        cur->_color = BLACK;
                        grandfather->_color = RED;
                    }
                    else//需要单旋
                    {
                        RotateL(grandfather);
                        parent->_color = BLACK;
                        grandfather->_color = RED;
                    }

                    break;
                }
            }
            else
                break;
        }

        _root->_color = BLACK;
        return make_pair(iterator(temp), true);
    }

    //begin的意义是返回红黑树的最小值，即最左边的树
    iterator begin()
    {
        Node* leftmin = _root;
        while (leftmin && leftmin->_left)
        {
            leftmin = leftmin->_left;
        }
        return iterator(leftmin);
    }

    iterator end()
    {
        return iterator(nullptr);
    }

    const_iterator begin() const
    {
        Node* leftmin = _root;
        while (leftmin && leftmin->_left)
        {
            leftmin = leftmin->_left;
        }
        return const_iterator(leftmin);
    }

    const_iterator end() const
    {
        return const_iterator(nullptr);
    }

    void RotateL(Node* Parent)//左单旋,具体原理看notie笔记
    {
        Node* parent = Parent;
        Node* cur = parent->_right;//左单旋，cur必定是parent的右边，具体画图理解

        parent->_right = cur->_left;
        if (cur->_left) {//如果cur的左子树有节点，就将左子树的父节点从cur变为parent
            cur->_left->_parent = parent;
        }
        cur->_left = parent;
        Node* ppnode = parent->_parent;
        if (parent == _root) {//parent为根节点时：
            _root = cur;
            parent->_parent = cur;
            cur->_parent = ppnode;
        }
        else
        {
            if (ppnode->_left == parent)//ppnode的左节点是parent
            {
                ppnode->_left = cur;
            }
            else if (ppnode->_right == parent)//ppnode的右节点是parent
            {
                ppnode->_right = cur;
            }
            parent->_parent = cur;
            cur->_parent = ppnode;
        }
    }
    void RotateR(Node* Parent)//右单旋,具体原理看notie笔记
    {
        Node* parent = Parent;
        Node* cur = parent->_left;//右单旋，cur必定是parent的左边，具体画图理解

        parent->_left = cur->_right;
        if (cur->_right) {//如果cur的右子树有节点，就将右子树的父节点从cur变为parent
            cur->_right->_parent = parent;
        }
        cur->_right = parent;
        Node* ppnode = parent->_parent;
        if (parent == _root) {//parent为根节点时：
            _root = cur;
            parent->_parent = cur;
            cur->_parent = ppnode;
        }
        else
        {
            if (ppnode->_left == parent)//ppnode的左节点是parent
            {
                ppnode->_left = cur;
            }
            else if (ppnode->_right == parent)//ppnode的右节点是parent
            {
                ppnode->_right = cur;
            }
            parent->_parent = cur;
            cur->_parent = ppnode;
        }
    }
    bool IsBanlance()
    {
        return IsBanlance(_root);
    }
    bool IsBanlance(Node* root)//注意: IsBanlance不是一个递归函数
    {
        //1.不能有连续的红节点
        //2.每个路径的黑节点相同，设定一个基准值去比较
        if (root == nullptr)
            return true;
        if (root->_color != BLACK)//传入的只会是根节点，如果根节点不是黑节点则错误
            return false;


        //设置基准值
        int benchmark = 0;
        Node* cur = root;
        while (cur)
        {
            if (cur->_color == BLACK)
                benchmark++;
            cur = cur->_left;
        }

        return Checkcolor(root->_left, 1, benchmark) && Checkcolor(root->_right, 1, benchmark);
    }
    bool Checkcolor(Node* root, int blacknum, int benchmark)
    {
        if (root == nullptr)
        {
            //如果递归到空时，黑节点的数量与基准值对不上，则说明该树不为红黑树
            if (blacknum != benchmark)
            {
                cout << "黑节点的数量不对" << endl;
                return false;
            }
            return true;
        }
        //不能有连续的红节点
        if (root->_parent && root->_color == RED && root->_parent->_color == RED)
        {
            cout << "出现连续红节点" << endl;
            return false;
        }

        //遇到黑节点就对blacknum加加
        if (root->_color == BLACK)
            blacknum++;

        return Checkcolor(root->_left, blacknum, benchmark) &&
            Checkcolor(root->_right, blacknum, benchmark);
    }
};